// https://leetcode.cn/problems/reverse-linked-list-ii/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用虚拟头节点处理边界情况
// 2. 定位要反转区间的前驱节点和结束节点
// 3. 切断要反转的链表区间，记录前后连接点
// 4. 反转指定区间内的链表节点
// 5. 将反转后的子链表重新接入原链表
// 6. 时间复杂度：O(N)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include "LinkedListUtils.h"

class Solution 
{
private:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* prev = nullptr;
        ListNode* cur = head;

        while (cur != nullptr)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        
        return prev;
    }
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        auto leftPrev = dummy;
        for (int i = 1 ; i < left ; i++)
        {
            leftPrev = leftPrev->next;
        }

        auto rightNode = leftPrev;
        for (int i = left ; i <= right ; i++)
        {
            rightNode = rightNode->next;
        }

        auto midStart = leftPrev->next;
        auto midEnd = rightNode;
        auto rightNext = rightNode->next;
        midEnd->next = nullptr;

        auto newMidStart = reverseList(midStart);
        leftPrev->next = newMidStart;
        midStart->next = rightNext;

        ListNode* result = dummy->next;
        delete dummy;

        return result;
    }
};

int main()
{
    vector<int> head1 = {1,2,3,4,5}, head2 = {5};
    int left1 = 2, right1 = 4;
    int left2 = 1, right2 = 1;
    
    Solution sol;

    auto l1 = createLinkedList(head1);
    auto l2 = createLinkedList(head2);

    auto r1 = sol.reverseBetween(l1, left1, right1);
    auto r2 = sol.reverseBetween(l2, left2, right2);

    printLinkedList(r1);
    printLinkedList(r2);

    return 0;
}